The present invention relates generally to branch prediction in a processor pipeline, and more specifically, to branch prediction using a multi-way pattern history table (PHT) that is indexed using a global path vector (GPV).
Branch prediction is a performance-critical component of a pipelined high frequency processor. Branch prediction predicts the direction (i.e., taken versus not taken) and the target address of each taken branch instruction that is encountered in the pipeline. Branch prediction allows processing to continue along a branch's predicted path before resolution of the branch without having to wait for the outcome of the branch to be determined. However, a penalty is incurred if a branch is predicted incorrectly.
Branch prediction in a processor may be performed using a branch target buffer (BTB), which is a cache that stores branch and target information. Other structures, such as a branch history table (BHT), pattern history table (PHT), and multiple target table (MTT), can be included to store additional information that is used for branch direction and target prediction. Any such structures may be accessed in parallel with the BTB with the same latency as the BTB. The branch prediction structures can be accessed at different stages in a processor pipeline. For example, the branch prediction structures may be accessed asynchronously from instruction fetching in a lookahead manner, in parallel with instruction fetching, or after decoding instructions and determining the presence of branch instructions.
A BHT or PHT may use saturating counters as a state machine to predict the direction of branches. A BHT may be indexed and tagged based on instruction address of each branch in the BHT. A PHT may be indexed as a function of instruction address and global pattern history and may contain instruction address tags and/or pattern history tags. The global pattern history may represent the direction (taken or not-taken) of previous branches. Each PHT entry may be, for example, a 2-bit saturating counter. The PHT attempts to learn the dominant behavior of a branch when encountered with a particular global history pattern, or multiple branches with associated history patterns that map to the same table entry, and predict their direction.